package com.nav.util;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

public class WordSplitter implements Serializable {
	private static final long serialVersionUID = 1L;
	private Index index = new Index();
	private static class Index implements Serializable {
		private static final long serialVersionUID = 1L;
		boolean e;
		Index n[] = new Index[26];
		public void index(char c[], int i) {
			while(i < c.length && (c[i] < 'a' || c[i] > 'z'))
				i++;
			if(i >= c.length)
				e = true;
			else {
				if(n[c[i] - 'a'] == null)
					n[c[i] - 'a'] = new Index();
				n[c[i] - 'a'].index(c, i + 1);
			}
		}
	}
	public WordSplitter(String[] dictionary) {
		for(String w : dictionary)
			index.index(w.toCharArray(), 0);
	}
	public String[] split(String w) {
		char c[] = w.toCharArray();
		List<Integer> s = new ArrayList<Integer>();
		Index ni = index;
		boolean dw = true, pdw = false;
		int ei = -1;
		for(int i = 0; i <= c.length; i++) {
			if(ni == index) {
				if(i == c.length)
					continue;
				ni = c[i] < 'a' || c[i] > 'z' ? null : ni.n[c[i] - 'a'];
				if(ni == null) {
					ni = index;
					if(dw) {
						s.add(i);
						pdw = dw;
						dw = false;
					}
				} else {
					s.add(i);
					pdw = dw;
					dw = true;
					ei = -1;
				}
			} else {
				ni = (i == c.length || c[i] < 'a' || c[i] > 'z') ? null : ni.n[c[i] - 'a'];
				if(ni == null) {
					if(ei >= 0)
						i = ei;
					else {
						dw = false;
						i = pdw ? s.get(s.size() - 1) : s.remove(s.size() - 1);
					}
					ni = index;
				} else if(ni.e)
					ei = i;
			}
		}
		String ret[] = new String[s.size()];
		if(s.size() > 0) {
			int i = 0, si = s.get(i++);
			while(i < s.size()) {
				ei = s.get(i);
				ret[i - 1] = w.substring(si, ei);
				si = ei;
				i++;
			}
			ret[i - 1] = w.substring(si);
		}
		return ret;
	}
}
